本发明涉及最长匹配地址查询的方法和装置,更具体地,提出了一种在给出可用于搜索的查找表时对查找表进行增量更新的方法和装置。为了增加或删除查找表,在提供对查找表中的第一存储空间中存储的第一组路由的访问时,把第二组路由存储在查找表中的第二存储空间中。通过子树条目中存储的第一指针提供对第一存储空间的访问。将第二组路由存储到第二存储空间后,通过用指向第二存储空间的第二指针替换子树条目中存储的第一指针,将访问切换到第一存储空间中的第一组路由。
1.一种更新查询表的装置,包括:指向树中的第一子树入口的第一指针,通过所述第一指针提供对第一子树的第一存储空间中存储的第一组路由的访问;指向用于代替第一子树的第二子树的第二子树入口的第二指针,通过所述第二指针提供对第二子树的第二存储空间中存储的第二组路由的访问,所述第二组路由是通过复制所述第一组路由并添加至少一个新的路由或删除至少一个已有的路由而得到的;和被配置为通过用指向所述第二子树入口的所述第二指针替换指向所述第一子树入口的所述第一指针来提供对所述第二组路由的访问的逻辑。
2.根据权利要求1所述的装置,进一步包括:被配置为在替换所述第一指针后释放所述第一存储空间的释放逻辑。
3.根据权利要求1所述的装置,其特征在于所述第一组路由中的路由数量小于所述第二组路由中的路由数量。
4.根据权利要求1所述的装置,其特征在于所述第一组路由中的路由数量大于所述第二组路由中的路由数量。技术领域
因特网是由路由器连接的一组网络。路由器维护表示每个可能的目的网络,即接收的数据包应被转发到的下一跳的路由表。下一跳可以是另一个路由器或最终的目的地。
背景技术
在路由器中的端口接收的网际协议(“IP”)数据包包括一个IP目的地址。该IP目的地址是该IP数据包的最终目的地。目前,存在两种版本的IP,IP版本4(“IPv4”)和IP版本6(“IPv6”)。IPv4提供包含在用来存储IP目的地址的数据包中IP首部中的32位字段。根据存储在IP首部中的IP目的地址,如果目的地在本地网,路由器转发接收到的与下一跳路由器或最终目的地相连的数据包。一个32位的IPv4目的地址提供40亿个可能的路由。一个互连网路由器通常存储40亿个可能的路由中的5万个路由。然而,存储的路由数量会随着互连网的发展和IPv6的普及而增加。起初,IP地址空间分为A,B和C三类IP地址。每个IP地址空间分为网络地址和主机地址。A类可容纳126个网络,每个网络可包含16,000,000台主机。B类可容纳16382个网络,每个网络可包含64,000台主机,以及C类可容纳2,000,000个网络,每个网络可包含256台主机。然而,将IP地址空间划分为不同的类减少了可用IP地址的数量。C类只允许每个网络最多256台主机对于大多数组织来说太少了。因此,大多数组织分配到一个B类地址,多达64,000个主机地址,这些地址即使该组织用不了也不能由其它组织使用。具有B类IP地址的组织的主机都在16位最高有效位(“MSBs”)中存储相同的网络地址,例如27.32.xx.xx。引入无级域间路由(“CIDR”)以便释放未使用的IP主机地址。剩余的未使用网络分配给规模不同的组织。一个需要500个地址的组织得到500个连续的地址。例如,一个组织可以分配到以128.32.xx为起始的500个可用地址。自从引入了无级域间路由,增加了存储在路由器中的路由数量。无级域间路由需要最长前缀匹配来寻找相应路由来代替为找到相应的IP目的地址的下一跳而寻找匹配的网络地址。例如,因为128.32.4.xx可能已经分配给其它需要不同下一跳的组织,所以在B类IP地址的16MSB,例如128.xx.xx之后,不再停止寻找。一种用来查询关键字最长前缀匹配的方法是使用二叉树搜索。二叉树搜索与输入的32位逐位匹配到32层,需要32次搜索才能找到与32位关键字匹配的条目。另一种搜索匹配的方法是使用Patricia树。如果二叉树没有条目的叶子,Patricia树减少所需的搜索次数。Brodnick等人于1998年5月11日提交的题为“快速路由查询的方法和系统”,序号为PCT/SE98/00854的PCT申请中描述了有效地搜索与IP目的地址有关的下一跳的另一种方法。Brodnick描述的方法通过不再存储重复路由来减少所存储的下一跳的数量。通过减少下一跳的数量,减小了对内存的需求,因此路由查找表可以存储在快速超高速缓冲存储器中。Brodnick等人将二叉树划分为三层。将二叉树划分为三层使搜索次数减少到三。第一层中的索引条目表示搜索是否可以利用从条目获得的路由在第一层结束,或者该搜索必须利用IP目的地址另外的部分将继续到下一层。图1A说明了表示二叉树第一层的现有技术的64K(65536)位表。64K位表30代表在深度16层的二叉树的叶子或节点44,每个节点44对应一位。位表被划分为长度为16的位屏蔽。在64K位表中共有2¹²=4096个位屏蔽。图1A中显示了一个位屏蔽。如果有子树或路由索引存储在与节点44对应的指针数组中,则位表30中的一位赋置为“1”。如果该节点与前一节点44共享路由条目,则位表30中的一位赋置为“0”。图1B说明了在超高速缓冲存储器中实现查找表的当前技术。查找表包括码字数组36,基索引数组34和映射表40。图1B中还显示了32位IP地址38。针对位表30(图1A)中的每个位屏蔽,将码字46存储在码字数组36中。码字46包括一个6位的值46a和一个10位的位移46b。针对码字数组36的数组中的每四个码字46,将基索引42存储在基索引数组34中。码字数组36,基索引数组34和映射表40用来在指针数组(未显示)中选择指针。指针存储一个路由索引或一个索引以便执行进一步的搜索。通过在码字数组36中选择码字46和在基索引数组34中选择基索引42来在指针数组中选择一组指针。利用IP地址38的前12位50来选择码字46。利用IP地址38的前10位来选择基索引42。利用映射表32在一组指针中选择正确的指针。所选码字36中10位的值46b作为到映射表32的索引。映射表32将一个位屏蔽中的位数映射到4位的位移。该位移指定在指针数组中所选的一组指针中的指针。10位的值46b选择映射表32中的行,并且IP地址52的位19:16选择4位的位移54。这样,搜索指针需要下面的超高速缓冲存储器访问:(1)读取16位码字46;(2)读取16位基地址42;(3)从映射表32中读取4位位移54;(4)从指针索引读取指针,其中指针索引是基地址42,码字位移46a和4位位移54之和。二叉树的每一层需要同样的存储器访问。这样,3层的搜索需要访问存储器12次。
发明内容
Davidxa0A.Brown提交的代理案编号2037.2004-001,题为“长匹配地址查询的方法和装置”描述了用来执行多层搜索符合关键字的值的查找表。能够存储在查找表中的路由索引的数量由查找表中存储单元的数量来限制。根据本发明的原理,给出包括第一查询单元和第二查询单元的查找表。第一查询单元接收关键字并且通过第一单元中的多层搜索提供第一结果。第二查询单元接收关键字并且通过第二单元中的多层搜索提供第二结果。第一查询单元和第二查询单元二者都并行地接收关键字,但根据第一结果和第二结果,只有一个单元提供只存储在一个查询单元中的关键字的最终结果。根据存储在查找表中的最终结果的总数将最终结果分配到表中。关键字可以是IP地址,最终结果是IP地址的路由索引。由关键字索引的第一查询单元中的第一存储单元存储最终结果,由关键字索引的第二查询单元中的第二存储单元存储最终结果存储在第一查询单元的指示。第一查询单元和第二查询单元都包括多个映射程序层并且每一个映射程序层包括用于存储结果的存储单元。在一个实施例中,把与存储在第一查询单元中的多个映射程序层的任何一层中的单元中的关键词对应的最终结果转发到第二查询单元,并由第一查询单元提供。在另一个实施例中,由存储最终结果的查询单元提供与该关键字对应的最终结果。
附图说明
图1A示出代表二叉树第一层的现有技术的位表;图1B示出在超高速缓冲存储器中实现的现有技术的查找表;图2A示出根据本发明原理的最长匹配前缀查找表;图2B示出存储在图2A所示的查找表中的路由索引的二叉树表示;图3示出根据本发明原理的40位关键字的最长匹配前缀查找表;图4示出能够存储在图2A所示的直接映射的映射程序的映射程序条目的类型;图5示出对应图2B所示的映射程序层2112b中的节点的映射程序;图6A是子树的二叉树表示;图6B示出对应图6A所示的子树底层中的节点的图5所示的数据字段中存储的密集子树描述符。图7示出图5所示的ptr字段;图8示出图5所示的映射程序地址逻辑;图9是说明搜索最长匹配的步骤的流程图;图10A示出提供深度扩展的实施例;图10B示出图10A所示的实施例中的一个查找表;图10C示出通过提供深度扩展来增加可用于存储值的映射程序条目数量的另一个实施例;图10D示出图10C所示的实施例中的副查找表;图11A-B示出在图10A和10C所示查找表中的映射程序条目中图2B所示路由索引的二叉树表示中节点分配的二叉树表示。图12是说明在图10A和10C所示的查找表中的映射程序条目中分配值的方法的流程图;图13是说明搜索与图10C所示的查找表中一个映射程序条目中存储的搜索关键字对应的值的方法的流程图;图14是说明搜索与图10A所示的查找表中一个映射程序条目中存储的搜索关键字对应的值的方法的流程图;图15示出由第一映射程序层索引的第二映射程序层中稀疏子树和密集子树的二叉树表示;图16A-C示出在图5所示子树条目和图4所示子树条目中数据字段和指针字段的修改以便在子树条目中允许存储多个稀疏子树描述符;图17示出图8所示位移逻辑中稀疏模式子树逻辑以选择稀疏居住子树中节点的块位移;图18示出图17中位移逻辑中所示的稀疏模式逻辑;图19A-D示出在稀疏居住子树中为节点选择块位移;图20是说明图8所示指针逻辑中稀疏模式基本选择逻辑的方框图;图21示出在子树存储器中存储的密集子树描述符和稀疏子树描述符;图22是说明向为稀疏居住子树和密集居住子树中的节点存储路由的子树映射程序中的映射程序条目提供映射程序地址的方法的流程图;图23示出将要加到查找表的新路由的二叉树表示;图24示出更新处理器存储器中存储的路由;图25示出查找表中存储的图23所示的新路由;图26是说明向图25所示查找表中增加新路由的步骤的流程图。本发明前面所述的及其它目的,特征和优点将通过下面参考本发明实施例的具体描述更加显而易见,不同附图中的相同部分用同一参考符号表示。附图不必放大,强调只起说明本发明原理的作用。
具体实施方式
下面描述本发明的优选实施例。密集模式图2A示出根据本发明原理的最长匹配前缀查找表100。查找表100提供对应关键字104的路由索引102。路由索引102用来访问对应IP目的地址的下一跳。在图2A所示的实施例中,关键字104为32位,但是关键字104不必限制在32位。查找表100包括3个映射程序106a-c。每个映射程序106a-c包括独立的地址存储器。对应关键字104的路由索引102或缺省路由索引存储在映射程序106a-c之一的一个单元中。如果需要搜索多个映射程序,来自每个映射程序的映射程序输出110a-c存储在延迟存储器150a-c中,直到所有映射程序106a-c已访问了关键字。多路复用器108选择转发到多路复用器108输入端中的一个映射程序输出110a-c作为路由索引102。根据映射程序输出110a-c的最高有效位(“MSB”)来选择映射程序输出110a-c。仅当映射程序输出110a-c包括路由索引102时,将映射程序输出110a-c的MSB置为“1”。图2B说明了图2A所示的查找表100中映射程序106a-c中存储的条目的二叉树表示。结合图2A来描述图2B。32位关键字104可以表示为32层二叉树。二叉树实现需要32次搜索,以便按位向下搜索到32层。为减少搜索次数,将32层的二叉树分为每个映射程序层112a-c对应一个映射程序106a-c(图2A)的3个映射程序层112a-c。映射程序层1xa012a包括32层二叉树的前16层。然而,为简单起见,图2B中只显示了16层中的5层。映射程序层2xa0112b包括32层二叉树接下来的8层,图2B显示了8层中的3层。映射程序层3包括32层二叉树的最后8层,图1B显示了8层中的3层。每个映射程序层112a-c包括多个节点。将32层这样分配,使映射程序层1xa0112a中包括16层(关键字104的16MSB),映射程序层2xa0112b中包括8层以及映射程序层3中包括8层对当前存储器技术显然是最适宜的;然而,本发明不受这种配置的限制。取代对关键字104的前16位进行16次分别的逐位搜索,而是将与关键字104的前16位有关的路由索引102存储在映射程序106a中(图2A)。映射程序106a(图2A)直接由关键字104的前16位MSBs索引。根据前一个映射程序106a是否存储了用于访问与关键字104有关的下一跳信息的路由索引102来搜索接下来的映射程序106b。如图2B所示,映射程序层1xa0112a所示的节点或叶子包括分别标为r0和r1的两个路由114,116,以及分别标为s0和s1的指向映射程序层2xa0112b中130⁴和130²³的两个指针。对应每个路由114,116的路由索引102存储在L1映射程序106a中。另外,为子树索引130⁴存储L2映射程序106b的地址指针120,为子树索引130²³存储L2映射106b的地址指针(未示出)。在映射程序106a中的映射程序条目140⁴中为子树索引130⁴存储的地址指针120表示为了寻找与关键字104有关的路由索引102所需的下一层的搜索。树中任何节点的值可以通过跟踪从根114开始的路径来确定。所示二叉树中的每个节点有两个子节点,右子节点和左子节点。如果父节点为“1”,选择右子节点。如果父节点为“0”,选择左子节点。跟踪从根114到节点116的路径,对于所有MSB置为“010”的关键字,r1作为路由索引102存储在L1映射程序106a中。跟踪从根114到s0节点130⁴的路径,对于所有MSBs置为“00011”的关键字,s0存储在L1映射程序106a中。L1映射106a是直接映射的映射程序并且存储映射程序层1xa0112a的底层的每个底层节点或叶子的路由索引102。映射程序层1xa0112a的底层是32层二叉树的第16层。第16层有64K个节点。但是,为了说明的目的,所示映射程序层1xa0112a的底层作为32层二叉树的第五层显示。L1映射程序106a所示的路由索引102对应映射程序层1xa0112a的第五层节点130¹-130³²。跟踪从根节点114到第五层节点130¹,130²,130³的路径,路由索引102为r0。因此r0存储在L1映射程序106a的位置140¹,140²,140³中;即在索引00000,00001和00010。节点130⁴存储子树索引s0,因此s0存储在L1映射程序106a中地址为00011的位置140⁴。类似地,第五层节点130⁵-130⁸的路由索引102是r0,因此r0存储在L1映射程序106a中地址为00100,00101,00110和00111的位置140⁵,140⁶,140⁷,140⁸。对应第五层节点130⁹-130¹²的路由索引102是r1,因此r1存储在L1映射程序106a中地址为01000和01001的位置140⁹,140¹⁰。在L1映射程序106a的每个位置存储直接分配给第五层节点300¹-300³²或通过第五层节点300^1-32的父节点分配或指向下一个映射程序106b-c的地址指针的路由索引102。映射程序层3xa0106c包括在32层二叉树底层的节点138的主节点h0和在节点140的主节点h1。对主节点的搜索需要搜索关键字104的所有位。如图2A所示,h0的路由索引102存储在L3映射程序106c中的位置146⁴中。与L1映射程序106a不同,L2映射程序106b和L3映射程序106c不是直接映射。在映射程序106b和106c中,不为每个可能的输入而存储路由索引102。仅当节点的路由索引102与映射程序106b-c中存储的前一个路由索引102不同时才存储路由索引102。请看映射程序层2112b中所示的第一子树A中的第三层节点,节点132¹和节点132²的路由索引102是r0,因此r0对应的路由索引存储在L2映射程序106b中的节点132¹和节点132²对应的位置142¹中。节点132²的子树索引存储在位置142²中。与第三层节点132⁴和第三层节点132⁵和132⁶有关的路由索引102为r0,与存储前一个节点132²的s0不同,r0存储在L2映射程序106b中的下一个位置142³。因为节点132⁷不与前一节点132⁶共享同一路由,所以对应节点132⁷的路由r2存储在L2映射程序106b中的位置142⁴中。为下一个第三层的节点132⁷存储子树索引s3,因此,s3存储在L2映射程序106b中的位置142⁵中。由于仅当与前一节点的路由不同时才存储路由索引,因此减少了用于存储路由索引102所需的内存。如图所示,只需要L2映射程序106b中的5个位置来存储映射层2112b中第一子树A的8个第三层节点132^1-8对应的路由索引。对于非直接映射106b、106c将在后面结合图5详细描述。图3说明了根据本发明原理的对应40位关键字210的最长匹配前缀查找表200。在一个实施例中,40位关键字包括8位前缀和32位IP地址。8位前缀可以是与32位IP地址有关的虚拟专用网(“VPN”)的标识符。查找表200包括4个映射程序106a-d。如结合图2A所描述过的,映射程序106a是直接映射的映射程序。映射程序106b-d是间接映射。映射程序106a存储路由索引102或对应40位关键字210的16个MSB的L2映射程序106b的子树索引。这样,L1映射程序具有64K个可能的位置,第一映射程序层112a(图2B)的64K个节点中的每一个节点对应一个位置。存储在L1映射程序106a中对应位置的L1映射程序条目数据220a转发到管道208和L2间接映射程序106b。如果L1映射程序条目数据220a表明下一层的搜索需要利用关键字210b接下来的8位,那么根据关键字210b接下来的8位和L1映射程序条目数据220a在L2间接映射程序106b中执行搜索。第二层搜索的结果提供在转发到管道208和L3间接映射程序106c的L2映射程序条目数据220b上。根据关键字210c接下来的8位和L2映射程序条目数据220b,在L3间接映射程序106c中执行第三层搜索。搜索结果提供在转发到管道208和L4间接映射程序106d的L3映射程序条目数据220c上。L3映射程序条目数据220c根据关键字210d的最后8位和L3映射程序条目数据220c来确定是否在L4间接映射程序106d中执行第四层搜索。第四层的搜索结果提供在L4映射程序条目数据220d上。与关键字210的最长匹配前缀有关的路由索引102只存储在映射106a-d其中一个的一个位置。因此,转发到管道208的路由索引102只包含在映射程序条目数据220a-d之一中。如果在映射程序106a-d的其中一个中找到路由索引102,例如在106b中,则不需要对余下的映射程序106c-d进行搜索和访问。管道208包括用来选择映射程序条目数据220a-d之一中包含的路由索引102的多路复用器108(图2A)。例如,映射程序条目数据220a-d的MSB能够提供是否包含路由索引的指示。通过将管道208与映射程序106a-d结合使用,可以并行执行对具有不同关键字210的最长匹配前缀表200的多重搜索。管道208通过存储与40位关键字210有关的每个映射程序106a-d的映射程序条目数据220a-d,允许并行执行40位查找表200的多重搜索,直到映射106a-d的每个搜索都已完成,如果必要,寻找对应40位关键字210的路由索引。因此,对应所接收的IP地址的路由索引的搜索请求通过对直接映射的映射程序106a执行一次内存访问来发送给查找表200。对应于另一个关键字的路由索引的后继搜索可以在直接映射的映射程序106a的下一个内存访问循环时发送给查找表200。图4说明了能够存储在图3所示的直接映射的映射程序106a中的映射程序条目的类型。图2B所示的二叉树中任何节点对应的映射程序条目能够存储非条目300,路由条目302或子树条目描述符304。映射程序条目300,302,304中每一种类型包括一个子树标记306。子树标记306的状态表示映射程序条目是否为子树条目描述符304。如果子树标记306置为“1”,映射程序条目是子树描述符304并且包括子树索引312。子树索引312是下一个非直接映射的映射程序106b-d中存储的子树条目描述符304的地址。子树条目将在后面结合图4进行描述。如果子树标记306为“0”,将检查非条目标记314来确定映射程序条目是非条目300还是路由条目302。如果非条目标记314是“0”,该条目则是非条目300。如果非条目标记314为“1”,该条目则是路由条目302,并且在路由索引字段310存储中与关键字104有关的路由索引102(图3)。多路复用器108(图2A)利用子树标记306来选择包括路由索引102(图3)的映射程序条目数据220a-d。图5说明了对应图2B所示的映射层2112b中的节点的映射程序106b。映射106b包括子树内存400,映射程序地址逻辑402和子树映射程序418。把由存储在映射程序106a中的关键字210a的第一部分选择的子树索引312转发到子树内存400。子树内存400包括由子树索引312选择的子树条目404。子树条目404包括数据字段406和指针字段408。返回图2B,子树条目404对应映射程序层2112b所示的一个子树的底层。如果映射程序层2112b有8层,每个子树(未示出)的底层具有最多256条路由,每个节点一个路由。继续到图5,子树条目404提供对与子树底层上的每个节点对应的256个可能的路由索引102(图3)的访问。路由索引102(图3)存储在子树映射程序418中。为提供对256个可能的路由索引的访问,密集子树描述符存储在数据字段406中。数据字段406有256位宽,为在子树底层的每个节点提供一位。数据字段将在后面结合图6A和图6B详细描述。指针字段408有256位宽,允许存储16个16位指针,每个指针存储子树映射程序418中16个相邻映射程序条目的基地址,以便提供对256个路由索引的访问。因此,指针字段408可以为子树底层中的每个节点间接地提供到子树映射程序418中的映射程序条目的指针。将结合图6详细描述指针字段408。把存储在数据字段406的密集子树描述符中的子树数据412和存储在指针字段408中的子树指针414转发到映射程序地址逻辑402。映射程序地址逻辑402还接收关键字210b的下一部分(接下来的8位)。映射程序地址逻辑402根据与子树有关的关键字212b接下来的8位,子树数据412和子树指针414来确定与子树底层中的节点有关的映射程序条目的映射程序地址416。映射程序地址416在子树映射程序418中选择映射程序条目。子树映射程序418包括直接映射的映射程序106a的与结合图4所述类型相同的映射程序条目。映射程序数据条目220b的内容确定是否需要后继搜索。如果映射程序条目数据220b包括表明在下一个映射层112c(图2B)还有另一个子树条目404的子树索引312(图4),则需要后继搜索。关键字210b的第二部分选择所选子树底层中的节点。子树指针414选择与子树中的节点有关的基地址,子树数据412选择与基地址有关的映射条目模块中的位移。映射程序地址逻辑402将结合图7在后面描述。图6A是子树的二叉树表示。所示子树包括5层。该子树包括三个路由索引r1,r2和r3以及两个子树索引s0和s1。子树底层上有32个节点500¹-500³²。下面的表1显示了与底层中的每个节点500¹-500³²有关的路由索引或子树索引。ntent="drawing" img-format="tif" inline="no" orientation="portrait" wi="356"/>表1图6说明了对应图6A所示的子树底层中的节点的图5所示的数据字段406中存储的密集子树描述符。数据字段406包括32位,图6A所示的子树底层中的每个节点500对应一位。位502¹-502³²在数据字段406中是这样分配的:如果要使用前一个节点的路由索引,那么数据字段中的一位设定为‘0’,如果使用存储在子树映射程序418(图5)中的下一个路由索引,那么设定‘1’递增到下一个映射条目地址。除非指定了路由,否则数据字段402中的第一位选择存储在映射程序条目504¹中的缺省路由r0。这样,由于没有指定的路由,把位502¹设定为‘0’来选择缺省路由。为接下来三个节点500²-500⁴选择映射程序条目504¹中存储的缺省路由r0,因此,在数据字段406中的对应位502²-502⁴被设定为“0”,以使用502¹使用的前一个路由索引。在节点500⁵存在路由改变。节点500⁶共享用于映射程序条目504²中存储的节点500⁵的路由r1。因此位502⁵是‘1’表示路由改变,以便在子树映射程序418(图5)中选择映射程序条目504²。位502⁶是‘0’表示把502⁵中存储的路由索引用于该节点。不为节点500⁷提供路由,因此,存在着路由变化,并且在位502⁷中存储‘1’来表示需要在子树映射程序418(图5)中的映射程序条目504³存储缺省路由r0。节点500⁸与前一个节点500⁷共享同一个路由,在子树映射程序418(图5)中不需要新的映射程序条目。对应节点500⁸的位502⁸设定为“0”。节点500⁹与前一个节点500⁸具有不同的路由,因此在子树映射程序418(图5)中需要新的映射程序条目。对应节点500⁹的位502⁹设定为“1”,并且将存储r2的映射程序条目504⁴添加到下一个相邻存储单元中的子树映射程序418(图5)。节点500¹⁰与前一个节点500⁹具有不同的路由,在子树映射程序418(图5)中需要新的路由条目。对应节点500¹⁰的位502¹⁰设定为“1”,并且将存储s0的映射程序条目504⁵添加到下一个相邻存储单元中的子树映射程序418(图5)。节点500¹¹与前一个节点500¹⁰具有不同的路由,在子树映射程序418(图5)中需要新的映射程序条目。对应节点500¹¹的位502¹¹设定为“1”,并且将存储r2的映射程序条目504⁶添加到下一个相邻存储单元中的子树映射程序418(图5)。节点500¹²和500¹³共享与前一个节点500¹¹相同的路由,在子树映射程序418(图5)中不需要新的映射程序条目。在数据字段406中把对应于节点500¹²的位502¹²和对应于节点500¹³的位502¹³设定为‘0’。节点500¹⁴与前一个节点500¹³具有不同的路由,在子树映射程序418(图5)中需要新的映射程序条目。数据字段406中对应节点500¹⁴的位502¹⁴设定为‘1’,并且把存储s1的映射程序条目504⁷添加到下一个相邻存储单元中的子树映射程序418(图5)。节点500¹⁵与前一个节点500¹⁴具有不同的路由,在子树映射程序418(图5)中需要新的映射程序条目。数据字段406中对应节点500¹⁵的位502¹⁵设定为‘1’,并且将存储r2的映射程序条目504⁸添加到下一个相邻存储单元中的子树映射程序418(图5)。节点500¹⁶与前一个节点500¹⁵共享同一个路由,在子树映射程序418(图5)中不需要新的映射程序条目。节点500¹⁷与前一个节点500¹⁶具有不同的路由,在子树映射程序418(图5)中需要新的映射程序条目。将数据字段406中对应节点500¹⁷的位502¹⁷设定为‘1’,并且将存储r3的映射程序条目504⁹添加到下一个相邻存储单元中的子树映射418(图5)。节点500¹⁸-500³²全部与前一个节点500¹⁷共享相同的路由,在子树映射程序418(图5)中不需要新的映射程序条目。将对应的位502¹⁸-502³²设定为‘0’。这样就需要9个映射程序条目504^1-9来存储32个节点500¹-500³²的路由条目302(图4)或子树条目304(图4)。通过计算在数据字段406中存储的密集子树描述符中存储的‘1’的数量在子树映射程序418(图5)中索引与节点500¹-500³²对应的映射程序条目504¹-504⁹。例如,为寻找对应节点500²⁸的映射程序条目504¹-504⁹,计算数据字段406的位502¹-502²⁸中存储‘1’的数量。‘1’的数量是8,并且对应的映射程序条目是从缺省路由开始的第八个位置,即映射程序条目504⁹。仅当路由发生变化时才存储映射程序条目的方法减少了子树映射程序418(图5)中每个子树映射程序条目504¹-504⁹的数量。图7说明了图5所示的指针字段408。指针字段408包括用于存储子树映射程序418(图5)中几组16个相邻映射程序条目位置504¹-504¹⁶组(图6B)的基地址的块基地址字段600¹,600²。在16个相邻映射程序条目的组602¹,602²的子树映射程序418(图5)中分配内存。8层的子树可以具有多达256个不同路由,需要16个组602¹,602²来存储所有256个路由。根据子树的路由数量来确定所需组602的数量。通过从块基地址的空闲列表中(未显示)删除块基地址602¹,602²来将组602分配给特定的子树。为内存提供地址空闲列表的方法是已知的技术。通过分配16个映射程序条目504^1-16的内存块,由于所分配的16个位置是相邻的,所以子树映射程序418(图5)中的内存易于管理。图8说明了图5所示的映射程序地址逻辑402。映射程序地址逻辑402包括位移逻辑700,指针逻辑702和加法器逻辑704。位移逻辑700包括节点选择逻辑706和“1”计数逻辑708。指针逻辑包括基地址选择逻辑710。节点选择逻辑706选择在子树数据412中对应8位关键字210b的节点500(图6B)。相应的节点数通过节点选择718转发到‘1’计数逻辑708。‘1’计数逻辑708累计子树数据字段406中存储的‘1’的数量,直到与所选节点500对应的位。‘1’的数量通过块选择712转发到指针逻辑702并且通过块位移714转发到加法器逻辑704。需要8位宽的计数字段的256位子树数据字段406中最大可存储256个“1”。8位计数字段分为两个字段,提供块选择712的4个MSB和提供块位移714的4个最低有效位(“LSB”)。例如,如果8位的关键字210b为‘01000100’,为选择节点数68并且共有27个“1”存储在子树数据42的前68位,计数结果为ICxa0Hex(00011100),MSB(0001);即块选择714选择块602¹(图6)和LSB(1100);即基块位移选择映射程序条目504¹¹(图6),即块502¹中的第12个条目。基地址选择逻辑710根据从位移逻辑700转发的块选择712从子树指针414中选择基地址716。加法器逻辑704将从位移逻辑700转发的块位移714累加到基地址716,并且提供映射程序地址416。映射程序地址416是映射程序106b-d中映射程序条目504(图6B)的索引。图9是根据本发明原理用于在查找表200中搜索关键字210(图3)的最长匹配前缀的步骤的流程图。在步骤800中,把关键字210a(图3)的第一部分作为索引转发到映射程序106a。处理过程继续到步骤802。在步骤802中,由关键字210a(图3)的第一部分索引的第一层映射程序中的映射程序条目504(图6B)中存储的映射程序条目数据220a(图3)确定是否需要继续对下一层进行搜索。如果需要,处理过程继续到步骤804。否则,第一层映射程序中索引的映射程序条目504(图6B)中的路由条目302(图4)存储该关键字的最长前缀路由并且处理过程继续到步骤808。在步骤804,搜索下一层映射程序106b-d。下一层映射程序的索引取决于前一层映射程序中索引的映射程序条目504(图6B)中子树条目描述符304(图4)中存储的子树索引312和关键字210b-d的下一部分。处理过程继续到步骤806。在步骤806中,下一层映射程序中的索引映射程序条目504(图6B)存储该关键字对应的最长前缀路由索引或表示需要进一步搜索的子树索引。如果需要进一步搜索,处理过程继续到步骤804。否则,处理过程继续到步骤808。在步骤808,把映射程序106a-d之一中的一个映射程序条目504(图6B)中存储的路由索引102(图3)作为路由索引102(图3)从查找表200转发。处理过程结束。深度扩展能够存储在图3所示查找表200中的路由索引102(图3)的数量受子树映射程序418(图5)中可用映射程序条目504(图6B)的数量的限制。例如,如果每个子树映射程序418(图5)包括128K个映射程序条目并且在查找表中有两个子树映射程序418(图5),那么查找表200中最多可以存储256K个路由索引102(图3)。具有128K个映射程序条目的子树映射程序418(图5)需要一个17位的索引。具有512K个映射程序条目的子树映射程序418(图5)需要一个19位的索引。查找表200中2个512K的子树映射程序418(图5)为32位IPv4目的地址的40亿个可能的路由索引102(图3)中1百万个提供了存储空间。通过提供多个查找表200可以增加用于存储路由索引102(图3)的映射程序条目504(图6B)的数量。可以在多个查找表中并行地搜索与查找表200之一中的子树映射程序418(图5)中的映射程序条目504(图6B)中存储的搜索关键字对应的值。图10A说明了深度扩展的实施例。示出两个查找表,一个为主查找表200a,另一个为副查找表200b。但是,查找表的数量不只限于所示的两个,可以增加一个以上的副查找表200b。以相同的搜索关键字210并行搜索查找表200a-d中的每一个。对应于搜索关键字210的路由索引102(图3)存储在查找表200a-d之一中的子树映射程序418(图5)中,或查找表200a和200b二者中的直接映射程序106a中。在完成对查找表200a和200b的并行搜索后,找到最终路由索引900。图10B说明了图10A所示实施例中的查找表200a中的一个。查找表200a-b中的每一个包括映射程序106a-d和已经结合图3针对查找表200描述过的管道208,以及驱动器逻辑902。查找表200a为与搜索关键字对应的路由索引在映射程序106a-d中执行多层搜索。每一层的搜索结果通过映射程序条目数据220a-d转发到管道208。管道208再将搜索结果904转发到驱动器逻辑902。每个查找表200a-b中映射程序106a中的映射程序条目504(图6B)存储子树条目304(图4),但只有主查找表200a的映射程序106a存储路由条目302(图4)。副查找表200b中映射程序106a中的映射程序条目504(图6B)代替路由条目302存储非条目300(图4)。将映射程序106a中的路由索引集中在一个查找表避免了为提供最终路由索引900的查找表的选择过程。这导致了副查找表200b中不能用于存储路由索引而只允许存储相同查找表的64K内存配置成主查找表或结合图3所述的副查找表。在另一个实施例中,可以提供没有映射程序106a的副查询设备。如果路由索引102(图3)存储在映射程序106a中的路由条目302(图4),那么搜索在主查找表200a中的映射程序106a中结束。如图10A所示,主查找表200a和副查找表200b共享最终路由索引900。存储了最终路由索引900的查找表200a,200b提供路由索引102(图3)。如果每个查找表200a,200b是独立的设备,共享最终路由索引900减小了每个设备的外部引脚数量。只有查找表200a,200b中的一个随时驱动最终路由索引。为避免两个查找表200a,200b中存储与搜索关键字210有关的路由索引而会使两个查找表同时驱动最终路由索引900的错误状态,每个查找表200a,200b存储一个设备代码。3位的设备代码允许扩展的查找表包括8个设备。驱动器逻辑902确定搜索结果904是否包括路由索引102(图3)。如果包括,查找表200a中的驱动器逻辑902发出试图通过总线请求信号(未示出)驱动最终路由索引900的信号。如果两个或更多的查找表200a,200b同时发出试图驱动路由索引信号的信号,那么由具有最低设备代码的查找表200a,200b中提供路由索引。通过使用总线请求信号来解决总线冲突的方法是熟知的技术。图10C说明了用来提供深度扩展以增加可用于存储与搜索关键字210对应的值的映射程序条目数量的另一个实施例。在图10C所示的实施例中,提供两个查找表200c-d来存储值,主表200c和副表200d。但是查找表的数量不只限于所示的两个,可以通过加入更多的副表200d来增加映射程序条目的数量。在查找表200c-d中并行执行对与搜索关键字[39:0]210对应的查找表200c-d之一中的映射程序条目中所存储的值的搜索。图10D说明了图10C所示的实施例中的副表200d。每个查找表包括结合图3针对查找表200描述的映射程序106a-d。每个查找表200c-d中映射程序106a中的映射程序条目存储子树条目304(图4)。每个查找表200c-d将映射程序106a中映射程序条目504(图6B)里存储的子树条目描述符304(图4)中存储的子树索引312转发到下一个映射程序106b-d。但是,路由索引102(图3)只存储在主查找表200c的映射程序106a中。无条目存储在副查找表200d中的映射程序106a中以避免在一个以上的查找表200b,200d中存储与该关键字对应的路由索引。副查找表200d中的多层搜索结果904转发到最终索引逻辑1004。最终索引逻辑1004将多层搜索结果904或从主查找表200c转发来的输入结果1000a作为输出结果1002a转发。如果路由索引102(图3)包括在多层搜索结果904中,那么将多层搜索的结果作为输出结果1002a转发。如果路由索引102(图3)包括在输入结果1000a中,那么将输入结果1000a作为输出结果1002a转发。如果路由索引102(图3)既不包括在输入结果1000a,也不包括在多层搜索结果904中,那么将多层搜索结果904作为输出结果1002a转发。如图10C所示,主查找表200c和副查找表200d通过标有输入结果1000a的公共总线相连。路由索引102(图3)只通过输出结果1002a从副查找表200d转发。如果有一个以上的副查找表200d,最后一个副查找表提供扩展查找表的路由索引102(图3)。本实施例可以避免实现结合图10A所述的多驱动器最终路由索引900的出现,但需要更多用于输入结果1000a的设备外部引脚。图11A-B说明了在查找表200a-b(图10A)或200c-d(图10C)中分配图2B所示路由的二叉树表示。图11A说明了主查找表200a(图10A)或200c(图10C)中存储的路由的二叉树表示。主查找表200a中不包括图2B所示路由的二叉树表示中所示的子树B。节点130¹-130²²和130^24-32在结合图3所述的查找表200a中的映射程序106a中编码。如果存储在主查找表200a中,那么在那里索引子树B的节点用“X”图形化地表示为已修剪子树。在主查找表200a中对应节点130²³的映射程序条目504(图6B)不再存储指向子树B的子树索引312(图4)。取而代之的是非条目300(图4)存储在主查找表200a中对应节点130²³的映射程序条目504(图6B)中,以表示对应节点130²³的映射程序条目存储在另一个副查找表200b的子树映射程序418(图5)中。图11B说明了存储在副查找表200b(图10A)或200d(图10C)中子树映射程序418(图5)中的映射程序条目504(图6B)的路由的二叉树表示。与图2B所示二叉树表示不同,存储在副查找表200b中的路由的二叉树表示不包括子树A。因此,节点130¹-130³和130⁵-130³²以如结合图2B所述的那样进行编码。对应副查找表200b中节点130⁴的映射程序条目504(图6B)不再存储指向子树A的子树索引312(图4)。取而代之的是对应副查找表200b中节点130⁴的映射程序条目存储非条目300(图4)以表示对应节点130⁴的映射程序条目存储在另一个查找表中。子树A对应的子树索引和主机138(图11A)对应的路由索引存储在主查找表200a中,并且子树B对应的子树索引和主机140(图11A)对应的路由索引存储在副查找表200b中。副查找表200b,200d只存储子树的结果;就是说,副查找表200b,200d不存储第一层映射程序106a中的结果。参考图11A和图11B,利用关键字210a的第一部分对主映射程序层11102a(图3)或副映射程序层11104a中任何节点130⁹-130¹²的搜索产生了主查找表200a,200c中映射程序106a中映射程序条目504(图6B)中路由条目302(图4)中存储的r1xa0116以及副查找表200b,200d中映射程序106a中映射程序条目504(图6B)中存储的非条目300(图4)。主查找表200a,200c中存储的路由条目302(图4)通过输入结果1000a转发到副查找表200b,200d并且通过输出结果1002a由副查找表200b,200d转发。利用关键字210a的第一部分对节点130⁴的搜索产生了主查找表200a中映射程序106a的映射程序条目504(图6B)中子树条目描述符304(图4)中存储的子树A的子树索引312(图4)。子树索引312转发到主查找表200a中的映射程序106b来继续对主查找表200a中存储的路由条目302(图4)进行搜索。利用关键字210的第一部分对节点130²³的搜索产生主查找表200a中映射程序106a的映射程序条目504(图6B)中存储的非条目300(图4)以及副查找表200b中映射程序106a的映射程序条目504(图6B)中存储子的树条目描述符304(图4)。因此,继续利用关键字210b的下一部分在副查找表200b的映射程序106b中搜索路由条目302(图4)。图12是说明图10A所示查找表200a-b中映射程序条目504(图6B)中存储的路由条目302(图4)的分配方法的流程图。同样的方法用于图10C所示的查找表200c-d。在查找表200a-b中存储之前,最初由处理器(未示出)在存储器中存储映射程序条目中要存储的路由条目302(图4)。当路由条目302(图4)存储在存储器中时,计算每个查找表200a-b(图10A)中要存储的路由条目302(图4)的数量。映射程序层1xa01104a(图11B)的路由条目302(图4)存储在查找表200a的映射程序106a中。映射程序层1xa01104a(图11B)的子树条目304(图4)存储在每个查找表200a-200b的映射程序106a中。在步骤1200中,为确定如何在查找表200a-b(图10A)中分配路由条目302(图4),需要计算每个查找表200a-200b(图10A)中映射程序106a的每个子树条目304(图4)中要存储的路由条目302(图4)的数量。当确定了存储路由条目302(图4)所需的映射程序条目504(图6B)的总数之后,处理过程继续到步骤1202。在步骤1202中,将要存储的子树的映射程序条目504(图6B)的总数除以查找表200a-b(图10A)的数量以确定存储在每个查找表200a-b(图10A)中的路由条目302(图4)的数量。处理过程继续到步骤1204。在步骤1204中,在所选查找表200a-b中子树映射程序418(图5)的映射程序条目504(图6B)中存储路由条目302(图4)。处理过程继续到步骤1206。在步骤1206中,如果在所选查找表200a-b中子树映射程序418(图5)的映射程序条目504(图6B)中存储的路由条目的数量小于1/n,其中n表示可用查找表200a-b(图10A)的数量,那么处理过程继续到步骤1024。否则,所选查找表200a-b已经存储了映射程序条目总数的1/n,并且处理过程继续到步骤1208。在步骤1208中,所选查找表200a-b存储映射程序条目总数的1/n,因为相应子树的路由索引不存储在当前所选的查找表中,所以任何剩余子树节点的非条目300(图4)存储在所选择的查找表200a-b中。处理过程继续到步骤1210。在步骤1210中,如果已经存储了全部路由条目,处理过程结束。否则,处理过程继续到步骤1212。在步骤1212中,选择下一个查找表200a-b(图10A)。处理过程继续到步骤1204。在搜索对应于IP地址的路由索引之前,在查找表200a-b(图10A)中分配路由条目。搜索是在查找表200a-b(图10A)中的每一个中并行执行的。用查找表200a-b(图10A)中的一个来描述实现对每个查找表并行搜索的方法。图13是说明利用搜索关键字搜索与图10C所示的查找表200c-d中的任何一个存储的搜索关键字对应值的方法的流程图。在步骤1300中,查找表200c-d(图10C)中的每一个接收搜索关键字210。查找表200c-d中的每一个中的映射程序106a搜索于关键字210a的第一部分对应的值。处理过程继续到步骤1302。在步骤1302中,读取映射程序106a中映射程序条目504(图6B)中存储的条目。主查找表200c中的映射程序条目504(图6B)可以存储非条目300(图4),路由条目302(图4)或子树条目描述符304(图4)。副查找表200d中的映射程序条目504可以存储非条目300(图4)和子树条目描述符304(图4)。如果相应的查找表200中的映射程序条目存储路由条目302(图4),该条目则是有效值,不需要进一步搜索查找表200c-d中的后继映射程序106b-d,处理过程继续到步骤1310。否则,处理过程继续到步骤1304。在步骤1304中,如果条目存储了子树条目描述符304(图4),那么需要进一步搜索查找表200c-d并且处理过程继续到步骤1306。否则,该条目存储非条目,表示不需要进一步的搜索,处理过程继续到步骤1310。在步骤1306中,在所选子树中继续搜索。根据关键字210b-d的下一部分和从上一层的搜索得到的子树索引312(图4)来搜索下一层映射程序106b-d(图3)。处理过程继续到步骤1308。在步骤1308中,根据从当前层映射程序106b-d中搜索得到的映射程序条目来确定是否继续执行搜索。如果映射程序条目504(图6B)存储了子树条目描述符304(图4),搜索继续到下一层映射程序106b-d并且处理过程继续到步骤1306。如果映射程序条目504(图6B)没有存储子树条目描述符304(图4),则不需要作进一步搜索,处理过程继续到步骤1310。在步骤1310中,把搜索结果与从另一个查找表接收的输入结果作比较。例如,如果查找表是副查找表200d,那么把从主查找表200c中搜索产生的输入结果通过输入结果1000a转发到查找表200d,并且与副查找表200d的搜索结果作比较。处理过程继续到步骤1312。在步骤1312中,如果输入结果1000a与当前查找表200d中的搜索结果不同,处理过程继续到步骤1314。如果输入结果1000a与当前查找表200d中的搜索结果相同,在分开的查找表200c-d中的映射程序条目504(图6B)中已经存储这两个有效的结果。不应该相同的关键字210来存储两个有效结果,处理过程继续到步骤1316。在步骤1314中,检查输入结果1000a来确定它是否有效。如果输入结果1000a是路由条目302(图4),那么它是有效的。如果输入结果1000a是非条目300(图4)或子树条目描述符304(图4),那么它是无效的。子树条目描述符304(图4),路由条目302(图4)和非条目300(图4)已经结合图4描述过了。如果输入结果1000a无效,处理过程继续到步骤1318。否则,处理过程继续到步骤1320。在步骤1318中,输入结果1000a有效,而从当前查找表200d中搜索得到的结果无效。输入结果1000a通过输出结果1002a从当前查找表200d转发。如果当前查找表200d是最后一个查找表,那么输入结果1000a作为路由索引102(图3)转发,或者作为输入结果1000a转发到下一个查找表。处理过程结束。在步骤1316中,在不同的查找表中存储关键字的两个有效的结果值。在查找表200c-d中存储路由条目期间发生错误时,生成错误代码以便能够纠错。处理过程结束。在步骤1320中,来自当前查找表200d的搜索结果和输入结果1000a都无效。即使无效,也将当前查找表200d的搜索结果作为输入结果1000a转发到下一个查找表。处理过程结束。图14是说明搜索与图10A所示的查找表200a-b之一中存储的搜索关键字对应的值的方法的流程图。在步骤1340中,在两个查找表200a-b中的第一层映射程序106a搜索与关键字210a的第一部分对应的值。处理过程继续到步骤1342。在步骤1342中,如果利用关键字210a的第一部分搜索第一层映射程序106a后找到了有效的结果值,则处理过程继续到步骤1352。否则,处理过程继续到步骤1344。在步骤1344中,如果利用关键字210a的第一部分搜索第一层映射程序106a得到的值是子树条目描述符304(图4),处理过程继续到步骤1346。否则,当前查找表中不存储关键字的有效值,处理过程结束。在步骤1346中,继续在以搜索上一层映射程序期间找到的子树条目描述符304(图4)中标识的子树中搜索有效值。根据关键字210b-c的下一部分和从搜索下一层得到的子树选择在下一层映射程序中搜索一个值。处理过程继续到步骤1348。在步骤1348中,搜索结果确定是否需要对下一层进行搜索。从当前搜索得到的条目可以存储路由条目302,非条目300(图4)或子树条目描述符304(图4)。如果条目存储了子树条目描述符304(图4),则需要进一步的搜索并且处理过程继续到步骤1346。如果条目没有存储子树条目描述符304(图4),处理过程继续到步骤1350。在步骤1350中,如果条目存储了路由索引102(图3),处理过程继续到步骤1352。否则,将条目存储在另一个查找表中。处理过程结束。在步骤1352中,与该关键字对应的有效值存储在当前查找表中。有效值作为对应于该关键字的路由索引102(图3)转发。处理过程结束。稀疏模式返回图5,子树条目404对多达256个可能的路由索引中的每一个提供访问,256个节点字树中每个节点一个。路由索引存储在子树映射程序418(图5)中的映射程序条目504¹-504ⁿ中。根据子树条目404中数据字段406中存储的密集子树描述符和指针字段408中存储的子树指针确定在子树映射程序418(图5)中映射程序条目504(图6B)的映射程序地址416。密集子树描述符的格式已经结合图6A-6B描述过了。密集子树描述符为256个节点的子树中每个节点存储一个节点位502(图6B)。但是,所有子树针对256个节点中的每一个具有不同的路由索引,例如,一个子树可能只有一个路由索引。图15说明了由第一映射程序层112a中的子树条目304索引的第二层映射程序层112b中稀疏子树A和密集子树B的二叉树表示。映射程序106a中s1的子树条目描述符304(图4)存储子树A的子树条目404的子树索引312。映射程序106a中s0的子树条目描述符304(图4)存储子树B的子树条目404的子树索引312。密集集中子树B有11个路由索引;即,r6-r16和6个子树条目;即,s2-s7。与存储路由条目302(图4)的映射程序条目504(图6B)和子树B的子树条目304(图4)对应的映射程序地址416在密集子树描述符中的编码已经结合图6B描述过了。稀疏集中子树存储两个路由索引;即r1和r2。如果它们存储在密集子树描述符中,那么整个子树条目404用来提供映射程序条目504(图6B)的三个映射程序地址416;即,r0,r1和r2。查找表200中存储的路由数量可以通过对多个稀疏子树描述符的其中一个稀疏子树描述符编码以及对子树条目404中密集子树描述符中的密集集中子树描述符编码来增加。密集集中子树有16个或更多个映射程序条目504(图6B),子树条目404中的数据字段406存储结合图6A-6B所述的密集子树描述符。稀疏集中子树有15个或更少个映射程序条目504(图6B);子树条目404中的数据字段存储了多个稀疏子树描述符。通过提供在稀疏子树描述符中存储稀疏集中子树的能力,子树存储器400可以存储更多的子树并且查找表200中可以存储更多的路由条目。图16A-C说明了对图5所示子树条目404中数据字段406和指针字段408以及图4所示子树条目描述符304(图4)的更改,以便允许在子树条目404中存储多个稀疏子树描述符。转到图16A,以稀疏模式配置的子树条目404中的数据字段406包括多个稀疏子树描述符1400¹-1400ⁿ来代替结合图6B所述的子树的每个节点对应一位的密集子树描述符。每个稀疏子树描述符1400¹-1400ⁿ包括一个节点描述符1402¹-1402ⁿ。一个节点描述符1400¹-1402ⁿ是代表子树中完全已编码路由的一个9位值。节点描述符1402¹-1402ⁿ描述了子树中一个节点或多个节点。转到图16B,为支持存储稀疏子树描述符,在子树条目404的指针字段408增加模式字段1404。指针字段408还存储块基地址600¹和块基地址600²,每个块包括16个为每个子树条目404提供总共32个映射程序地址416的已分配映射程序地址416。模式字段1404存储模式值。模式字段1404中存储的模式值表示子树条目404中存储的稀疏子树描述符1400¹-1400ⁿ的数量和每个稀疏子树描述符1400¹-1400ⁿ中存储的节点描述符1402¹-1402ⁿ的数量。表2说明了每个模式对应的子树条目404的配置。ntent="drawing" img-format="tif" inline="no" orientation="portrait" wi="700"/>表2参见表2,例如,如果设置子树条目404中指针字段408的模式字段1404中存储的模式值为“4”,那么子树条目404中的每个稀疏子树描述符1400存储5到7个节点描述符1402¹-1402ⁿ。每个节点描述符1402¹-1402ⁿ存储9位。通过每个稀疏子树描述符1400¹-1400ⁿ的节点描述符1402¹-1402ⁿ的数量乘以9(每个节点描述符1402¹-1402ⁿ的位数)来计算存储在稀疏子树描述符1400中的总位数。计算模式4的每个稀疏子树描述符1400的位数后,具有7个节点描述符1402的稀疏子树描述符1400存储63位(7个节点描述符×9位=63)。数据字段406中的位数除以稀疏子树描述符1400¹-1400ⁿ的位数可以计算出每个子树条目404的稀疏子树描述符1400的数量。对于模式4,数据字段406中的位数为256并且稀疏子树描述符中的位数为63。因此稀疏子树描述符1400¹-1400ⁿ的数量为4(int(256/63)=4)。每个子树的节点数乘以每个子树条目404的子树数量可以得到每个子树条目404的节点描述符1402¹-1402ⁿ的总数。计算模式4,如果在稀疏子树描述符1400¹-1400ⁿ中存储了7个节点描述符1402¹-1402ⁿ,那么每个子树条目404的节点描述符1402的数量为28(7×4=28),并且如果每个子树描述符1400¹-1400ⁿ有5个节点描述符1402,则结果为20(5×4=20)。表2中的映射程序条目列表示子树条目404使用了多少子树映射程序418(图5)中的映射程序条目504(图6B)。通过将每个子树的节点加1并通过乘以稀疏子树描述符中的子树数量来计算映射程序值。每个子树节点加1是因为需要比每个子树节点数量多1个映射程序条目,以便存储子树的缺省条目。参见表2中模式4的一行,如果每个稀疏子树描述符1400有7个节点描述符1402,那么每个子树条目404需要32((7+1)×4=32)个映射程序条目,并且如果每个稀疏子树描述符1400有5个节点描述符1402,那么每个稀疏子树描述符1400需要24((5+1)×4=24)个节点描述符1402。因为在16个块递增中分配了子树映射程序418(图5)中的映射程序地址416,所以选择每个子树节点的数量和每个子树条目404的子树数量,以便每个子树条目404的节点描述符的最大数量不超过30。通过在指针字段408中存储两个块基地址600¹,600²来提供32个映射程序地址416。转到图16C,子树存储器400中的每个子树条目404可以配置成如结合图6B所述的密集模式或稀疏模式。通过提供表示子树条目404是否以密集模式或稀疏模式编码的标志,将结合图4所述的子树映射程序418(图5)中存储的密集模式的子树条目描述符304(图4)修改为稀疏模式。类型字段1406提供指示符。类型字段1406的状态表示子树条目404是按密集模式还是按稀疏模式配置。如果子树条目404以稀疏模式配置,那么稀疏子树描述符选择字段1408中存储的值和子树索引312用于选择稀疏子树描述符1400。稀疏子树描述符选择1408将结合图16在后面作详细描述。图17说明了用于提供块位移714来选择稀疏集中子树的节点的映射程序条目504(图6B)的图8所示的位移逻辑700中稀疏模式逻辑1502。稀疏模式逻辑1502根据子树条目404中稀疏子树描述符1400存储的节点描述符1402来提供块位移714。位移逻辑700还包括密集模式逻辑1500。密集模式逻辑1500包括节点选择706和用来提供密集集中子树中用于路由的块位移714的“1”计数逻辑708。密集模式逻辑1500已经结合图8描述过了。如果类型字段1406的状态表示子树条目404以稀疏模式配置,那么来自子树条目404的子树数据412转发到稀疏模式逻辑1502。结合图18描述稀疏模式子树逻辑1502。图18说明了图17中位移逻辑700所示的稀疏模式逻辑1502。稀疏模式逻辑1502包括子树选择逻辑1600,多路复用器1602,内容可编址存储器(“CAM”)1606以及转换逻辑1604。所选子树条目404中的数据字段406中存储的稀疏子树描述符1400¹-1400ⁿ通过子树数据412转发到位移逻辑700。位移逻辑700将稀疏子树描述符1400¹-1400ⁿ转发到稀疏模式逻辑1502中的多路复用器1602。由子树选择逻辑1600生成的选择1614来选择子树数据412中的一个稀疏子树描述符1400¹。子树选择逻辑1600根据从前一个映射程序层选择的映射程序条目转发的稀疏子树描述符选择1408的状态和所选子树条目404中的指针字段408中存储的模式1404生成选择1614,以便选择稀疏子树描述符1400¹。表3说明了所选稀疏子树描述符1400¹和从多路复用器1602通过所选择的稀疏子树描述符1610从对应模式4的子树条目404的多路复用器1602转发的相应的子树数据位412。参见表2中模式4的一行,在模式4中,子树条目404可以存储4个稀疏子树描述符。这4个稀疏子树描述符中的每一个可以以子树条目404的模式4存储。这4个稀疏子树描述符1400中的每一个有63位并且可以存储7到5个节点描述符1402。因此,这4个稀疏子树描述符1400中的每一个从63位的边界开始。第一个稀疏子树描述符1400¹存储在数据字段406的位62:0,第二个稀疏子树描述符1400²存储在数据字段406的位125:63,第三个稀疏子树描述符1400³存储在数据字段406的位188:126以及第四个稀疏子树描述符1400⁴存储在数据字段406的位251:189。稀疏子树描述符选择1408选择数据字段406中的相应位。例如,看表3,如果稀疏子树描述符选择1408是“0001”,那么选择第二个稀疏子树描述符1400²并且通过多路复用器1602将256位子树数据412的位125:63从所选择的稀疏子树描述符1610转发到转换逻辑1604。xa0xa0稀疏子树描述符选择
xa0xa0子树数据
xa0xa0稀疏子树描述符
xa0xa00000
xa0xa0Bitsxa062:0
xa0xa01
xa0xa00001
xa0xa0Bitsxa0125:63
xa0xa02
xa0xa00010

xa0xa0Bits
xa0xa0188:126
xa0xa03

xa0xa00011

xa0xa0Bits
xa0xa0251:189
xa0xa04

表3子树存储器400中的每个子树条目404可以配置成稀疏模式或密集模式。以稀疏模式配置的每个子树条目404可以配置为能够通过模式1404存储每个稀疏子树描述符1400的不同数量的节点描述符1402。以稀疏模式配置的子树条目404中所有稀疏子树描述符1400存储每个稀疏子树描述符1400相同数量的节点描述符1402。可以对节点描述符1402编码以表示子树中的多个节点。节点描述符1402表示的多个8位节点通过屏蔽8位中的一些位来识别。为取代利用每个节点描述符1402存储屏蔽位,使用9位节点描述符1402对节点描述符1402表示的8位宽的节点进行完全编码。使用运行比特长度编码来以9位宽的节点描述符1402对8位宽的节点编码。运行比特长度编码可以识别8位节点中的哪些位被屏蔽了。转换逻辑1604将所选稀疏子树描述符1400中存储的9位宽的节点描述符1402¹-1402ⁿ转换为包括置为“X”位(任意值)的8位CAM值1612并且将8位CAM值1612装载到CAMxa01606。表4显示了通过转换逻辑1604将9位节点描述符1402转换为8位CAM值1612的例子。xa0xa08位值
xa0xa09位代码
xa0xa0101100XX
xa0xa0101100100
xa0xa0100XXXXX
xa0xa0100100000
xa0xa0001111XX
xa0xa0001111100
xa0xa00011XXXX
xa0xa0001110000
表49位代码列说明了节点描述符1402中存储的值。看表4的第一行,节点描述符1402中存储的9位代码为“101100100”并且对应的8位值“101100XX”存储在CAMxa01606中。转换逻辑1604通过在9位代码中从右到左搜索第一个为“1”的位来转换9位代码。在9位代码从右到左的位中,前两位为“0”,第三位为“1”。由于在第一个“1”的右边有两个“0”,因此转换逻辑1604将“100”转换为两个任意位(“XX”)。第一个“1”被忽略,余下的位直接复制到8位值的后几位。在表4中的第二行,节点描述符1402存储的9位代码为“100100000”。转换逻辑1604通过在9位代码中从右到左搜索第一个为“1”的位来转换9位代码。第5位存储“1”。9位代码被转换为其5位最低有效位(“LSBS”)设置为“任意值”(“X”)的8位值。通过使用9位运行比特长度编码存储节点描述符1402,使每个节点描述符1402所需的位数最少,因此增加了可以存储在查找表200中的节点描述符1402的数量。在9位节点描述符1402转换为8位值之后,转换逻辑1604将8位值载入CAMxa01606。8位值以与所选稀疏子树描述符1400中存储的节点描述符1402相同的顺序载入CAMxa01606,即,从最短到最长的匹配。CAMxa01606提供用来存储每个稀疏子树描述符1400的最大编号节点描述符1402的存储空间。因此,CAMxa01606为8位宽16个条目深,以便能提供15个条目来存储模式5的稀疏子树描述符1400的节点描述符1402的最大编号以及缺省的映射程序地址。CAMxa01606具有三进制功能和内置的多匹配分解器。相对于提供真正的内容地址存储器,小容量的CAMxa01606可以利用逻辑门来实现,即,CAMxa01606可以通过仿真CAM的硬件电路来实现。稀疏子树描述符1400中存储的节点描述符1402的数量确定了存储稀疏子树描述符1400的子树条目404。在特定模式范围内存储节点描述符1402的稀疏子树描述符1400存储在相同的子树条目404中。为每个子树的缺省路由计算缺省映射程序地址。缺省的8位值永久地存储在CAMxa01606的第一单元以计算缺省的映射程序地址。在所选稀疏子树1400对应的8位值载入CAMxa01606之后,利用关键字210b的下一部分搜索CAMxa01606。选定与关键字210b的下一部分中最大位数匹配的CAMxa01606中的条目。从搜索CAM得到的匹配地址作为块位移714转发。块位移714用来确定与子树映射程序418(图5)中所存储路由对应的映射程序条目的映射程序地址416。图19A-D说明了对稀疏集中子树1700中一个节点的块位移714的选择。图17A用图形表示了稀疏集中子树1700中的路由。子树1700中的节点对应三个路由r0,r1和r2之一,r0是子树1700的缺省路由。以稀疏子树描述符1400中的节点描述符1402¹和1402²编码r1,r2两个路由。缺省路由r0的值永久保存在CAMxa01606中的第一条目1702中。参见表2,具有两个节点描述符1402的稀疏子树描述符1400存储在模式字段1404为“1”的子树条目404中。在子树1700中,r2对应所有与10xxxxxx匹配的节点,r1对应所有与010xxxxx匹配的节点。为了最小化用来描述稀疏子树描述符1400中每个路由的每个节点描述符1402¹,1402²所需的位数,使用运行比特长度编码对节点描述符1402¹,1402²进行编码。用于编码的方法比用于对节点进行完全编码所用位数多1位。在第一个“X”(“任意值”)的位置插入“1”并且其余X位编码为“0”。这样,路由10xxxxxx被翻译为10100000,路由010xxxxx被翻译为010100000。图19B说明了节点描述符1402¹和1402²在稀疏子树描述符1400中的存储。因为有两个节点描述符1402¹和1402²存储在稀疏子树描述符1400中,所以节点描述符1402¹和1402²存储在模式字段1404设置为“1”的子树条目404中。因为r1需要与前三位匹配,而r2需要与前两位匹配,所以子树的最长匹配为r1。节点1402¹和1402²按从最短到最长的匹配顺序存储在稀疏子树描述符1400中,其中r2的节点描述符1402¹存储在第一位,r1的节点描述符1402²存储在下一位。图19C说明了节点描述符1402²向8位屏蔽值1706的转换。在从左到右的节点描述符位1708¹-1708⁹中,第一个“1”存储在位1708⁶,它标志着8位被屏蔽值1706的屏蔽位的结束。执行下面的位转换来实现节点描述符1402²向8位被屏蔽值1706的转换。存储在节点描述符1708¹位的“0”转换为“X”并且存储在8位被屏蔽值1710¹位。存储在节点描述符1708²位的“0”转换为“X”并且存储在8位被屏蔽值1710²位。存储在节点描述符1708³位的“0”转换为“X”并且存储在8位被屏蔽值1710³位。存储在节点描述符1708⁴位的“0”转换为“X”并且存储在8位被屏蔽值1710⁴位。存储在节点描述符1708⁵位的“0”转换为“X”并且存储在8位被屏蔽值1710⁵位。存储在节点描述符1708⁶位的“1”被忽略。存储在节点描述符1708⁷位的“0”存储在8位被屏蔽值1710⁶位。存储在节点描述符1708⁸位的“1”存储在8位被屏蔽值1710⁷位。存储在节点描述符1708⁹位的“0”存储在8位被屏蔽值1710⁸位。图19D说明了存储CAMxa01606中的节点描述符1402¹和1402²以及所选择的稀疏子树描述符1400的子树映射程序418(图5)中存储的对应的映射程序条目504¹-504³。将所选择的子树描述符1400中存储的9位节点描述符1402¹和1402²转换到转换逻辑1604(图18)中,并且载入CAMxa01606。CAMxa01606中第一个条目1702是图19A中子树1700所示的r0的缺省条目。第二个条目1704从所选择的稀疏子树描述符1400中存储的第一节点描述符1402¹转换。第二个条目1704是为r2转换的最短匹配。把所选择的子树描述符1400中存储的第二节点描述符1402²从010100000转换为010XXXXX并且存储在CAMxa01606的第三条目1706中。对CAMxa01606的搜索产生块位移714(图18)。块位移714用来确定子树映射程序418(图5)中存储的映射程序条目504¹-504³的映射程序地址416。利用存储最长匹配的条目1702,1704,1706的关键字210b的第二部分来搜索CAMxa01606。根据所选择的子树条目404中的指针字段408中存储的块基地址600¹,600¹之一将CAMxa01606提供的块位移714与子树基地址结合。图20是说明图8所示指针逻辑702中稀疏模式基选择逻辑1800的方框图。指针逻辑702选择用于计算子树映射程序418(图5)中映射程序条目504(图6B)的映射程序地址416的基地址716。指针逻辑702包括密集模式基选择逻辑710和稀疏模式基选择逻辑1800,根据从上一层映射程序层转发的子树条目描述符304(图4)中存储的类型1406的状态来选择其一。如前所述,类型1406的状态表示是否将子树配置为密集模式。如果子树条目404存储了多个稀疏子树描述符1400,稀疏模式基选择逻辑1800计算稀疏子树描述符1400的基地址716。稀疏模式基选择逻辑1800利用模式字段1404中存储的模式值1608和子树条目404中块基地址域600¹,600²中存储的子树指针414以及上一层映射程序层转发的子树条目描述符304(图4)中存储的稀疏子树描述符选择1408来计算基地址716。基地址716的计算如下:基地址(稀疏子树描述符)=块基地址+基位移其中,基位移=((1+节点/子树)×稀疏子树描述符选择)例如,为查找以稀疏模式4配置的子树条目404中2号子树的起始基地址716,首先计算基位移。2号子树对应的稀疏子树描述符选择1408为“1”并且节点/子树数为7(见表2)。基位移为8((1+7)×1)。每个块基地址600¹,600²是分配给子树条目404的16个映射程序地址块的基地址。2号子树对应的基位移是小于16的8,因此2号子树的块基地址是块基地址600¹并且稀疏子树描述符的基地址716是块基地址600¹+8。表5说明了以模式4配置的子树条目404中四个子树的每个子树基地址。xa0xa0子树基地址
xa0xa0子树
xa0xa0块基地址1+0
xa0xa01
xa0xa0块基地址2+8
xa0xa02
xa0xa0块基地址2+0
xa0xa03
xa0xa0块基地址2+8
xa0xa04
表5图21说明了存储在子树存储器400中的密集子树描述符和稀疏子树描述符。结合图15来描述图21。子树B(图21)的密集子树描述符存储在子树条目404¹的数据字段406¹。子树A(图21)的稀疏子树描述符1400¹存储在子树条目404²的数据字段406²。密集子树描述符存储结合图6B描述过的子树B底层中每个节点的节点位。稀疏模式描述符1400¹包括对应结合图19B描述过的路由r4和r5的节点描述符1402¹和1402²。子树索引312选择子树条目404¹,404²。s0(图15)的映射程序106a中映射程序条目504(图6B)中子树条目描述符304(图4)存储的子树索引312选择子树条目404¹。sxa01(图15)的映射程序106a中映射程序条目504(图6B)中子树条目描述符304(图4)存储的子树索引312选择子树条目404²。因此,子树存储器400可以存储稀疏子树和密集子树对应的子树条目404¹,404²。图22是说明用来向存储稀疏集中子树和密集集中子树中的节点的路由的子树映射程序418(图5)中的映射程序条目504(图6B)提供映射程序地址416(图5)的方法的流程图。任何子树条目404都可以存储多个稀疏子树描述符或一个密集子树描述符。根据路由在二叉树中的如何分布,可以对稀疏子树描述符和密集子树描述符进行任意组合。灵活地混合和匹配在子树存储器400中子树条目404中的稀疏模式和密集子树描述符可以更好地利用子树存储器400。在步骤1900中,从在上一映射程序层中选择的子树条目描述符304(图4)中存储的类型1406的状态来确定所选择的子树条目404的配置。如果子树条目404的类型配置为稀疏模式,处理过程继续到步骤1902。否则,处理过程继续到步骤1914。在步骤1902中,子树条目404的配置是稀疏模式。以稀疏模式配置的子树条目404存储多个稀疏子树描述符1400。根据模式字段1404的状态确定子树条目404中存储的稀疏子树描述符1400的数量。位移逻辑700中的稀疏模式逻辑1502根据从上一映射程序层转发的子树条目描述符304(图4)中存储的稀疏子树描述符选择1408和前面结合图14描述过的模式字段1404的内容来从子树条目404中选择稀疏子树描述符1400。处理过程继续到步骤1904。在步骤1904,所选择的稀疏子树描述符1400中的节点描述符1402中存储的9位编码值被转换为8位值并且按从最短到最长匹配的顺序存储在CAMxa01606中。处理过程继续到步骤1906。在步骤1906中,利用关键字210b的下一部分在CAMxa01606中搜索存储最长匹配的CAM条目。处理过程继续到步骤1908。在步骤1908中,把存储关键字210b下一部分的最长匹配的CAMxa01606中的位置的地址作为块位移714转发。块位移714用来计算子树映射程序418(图5)中映射程序条目504(图6B)的映射程序地址416(图5B)。处理过程继续到步骤1910。在步骤1910中,根据从上一映射程序层转发的子树条目描述符304(图4)中存储的稀疏子树描述符选择1408和所选择的子树条目404中存储的模式字段1404的内容来计算所选稀疏子树描述符1400对应的基地址716。处理过程继续到步骤1912。在步骤1912中,通过在加法器逻辑704(图8)中将块位移714和基地址716相加来计算映射程序地址416。通过子树映射程序418(图5)中的映射程序地址416识别的映射程序条目504存储路由条目302(图4)或子树条目描述符304(图4)。如果映射程序条目504(图6B)存储路由条目302(图4),那么搜索结束。如果映射程序条目504(图6B)存储子树条目描述符304(图4),那么继续在下一映射程序层搜索对应关键字210b的值。在步骤1914中,子树条目404以密集模式配置并且在数据字段406中存储一个密集子树描述符。通过统计前面结合图6B描述过的子树条目404中数据字段406中存储的密集子树描述符中“1”的数量来计算块位移714。处理过程继续到步骤1916。在步骤1916中,子树条目404在子树条目404中的指针字段408存储16个块基地址600。前面结合图8描述过的指针逻辑702中的密集模式基选择逻辑710选择块基指针600中的一个。处理过程继续到步骤1912。递增更新图23说明了在查找表200中添加新路由的二叉树表示。二叉树说明了查找表200中存储的对应映射程序层1xa02000,映射程序层2xa02002和映射程序层3xa02004的路由。映射程序层2xa02002存储子树A和B的路由。映射程序层3xa02004存储子树A₁,A₂,B₁和B₂的路由。s5表示子树映射程序418(图5)中存储的子树条目描述符304(图4)。s5对应的子树条目描述符304(图4)存储指向子树B₂的指针,子树B₂允许继续在映射程序层32004搜索关键字210的最长匹配路由。因为子树B₂2006只有两个路由,r6和h1,所以它是稀疏子树。因此,节点r6和h1对应的节点描述符1402(图16A)存储在已经结合图14A描述过的稀疏子树描述符1400中。因为在稀疏子树描述符1400中存储了两个节点描述符1402,所以子树B₂2006对应的稀疏子树描述符1400存储在子树存储器400中模式字段1404设置为“1”的子树条目404中。子树B₂’2008所示的新节点h2添加到查找表200中。因为子树B₂2006的新增路由使稀疏子树描述符1400中存储的节点描述符1402的数量从2增加到3,所以新路由h1不能直接添加到查找表的子树B₂2006中。向稀疏子树描述符1400增加节点描述符1402需要在模式字段1404设置为“2”的子树条目404中分配新的稀疏子树描述符1400。因此,增加路由h1需要用子树B₂’2008代替子树B₂2006。图24说明了处理器存储器2400中存储的更新路由。查找表200中存储的二叉树的拷贝也存储在与查找表200分离的处理器存储器2400中。存储子树B₂2006的路由复制到处理器存储器2400的子树B₂’2008并且向子树B₂’2008增加新路由h2。路由更新程序2402生成一系列路由更新指令2404,以便将子树B₂’2008添加到查找表200中并且将路由更新2404转发到表更新程序2406。表更新程序2406生成路由更新2402对应的表更新2410并且转发更新周期2412,以便利用路由更新2404来更新查找表200。更新周期2412将路由更新写入子树存储器400(图5)中相应的存储器位置和子树映射程序418中(图5)。返回图23,更新周期2412包括用来分配一部分子树映射程序418(图5)以存储映射程序条目504(图6B)中新子树B₂’2008对应的路由的指令。子树B₂’2008包括路由h1和r6以及新路由h2的映射程序条目504(图6B)中存储的路由条目。在子树B₂’2008的路由条目存储在子树映射程序418(图5)中的映射程序条目504(图6B)后,产生了这些路由对应的节点描述符1402并且存储在稀疏子树描述符1400中。稀疏子树描述符1400存储在子树条目404。子树条目404的模式1404与稀疏子树描述符1400中存储的节点描述符1402的数量有关。在子树B₂’2008的稀疏子树描述符1400存储在查找表200的子树存储器400的子树条目404中之后,s5代表的子树条目描述符304(图4)由指向子树B₂2006改为指向子树B₂’2008。当把子树B₂’2008添加到查找表时,可以通过s5访问子树B₂2006中存储的路由r6和h1。在子树B₂’2008存储到查找表中后,s5改为指向子树B₂’2008并且可以访问路由h1和r6和新路由h2。因此,当把新路由h2添加到查找表200中时,可以在子树B₂2006中继续搜索对应于路由h1和r6的路由索引。图25说明了查找表200中子树映射程序418b中的映射程序条目504c⁴中存储的图23所示的新路由h2。结合图24所示的二叉树表示来描述图25。映射程序层22002中的子树B有3个路由;即r3,s4和s5。因为子树B的路由少于16个,所以它是稀疏子树。子树Bxa0r3,s4和s5的节点描述符1402a¹-1402a³存储在子树存储器400a中子树条目404a中的稀疏子树描述符1400a¹中。子树映射程序418a中存储子树B中每个路由对应的映射程序条目504a²-504a⁴。子树映射程序418a中的映射程序条目504a¹存储子树B的缺省路由。每个映射程序条目504a²-504a⁴存储该节点的路由条目302(图4)或子树条目描述符304(图4)。504a³中存储路由s4的子树条目描述符304(图4),504a⁴中存储s5的子树条目描述符304(图4)。映射程序条目504a⁴中存储的s5为子树存储器400b提供子树索引312b,以便开始下一层搜索;即对映射程序层32004的搜索。子树B₂有两个路由,即h1和r6,所以它也是稀疏子树。节点描述符1402b¹-1402b²存储在子树存储器400b中的子树条目404b中的稀疏子树描述符1400b¹中。子树B₂的每个路由存储在映射程序条目504b²-504b³中并且子树B₂的缺省路由存储在映射程序条目504b¹中。为在子树B₂2006中搜索路由h1,将保存了用来存储路由s5的节点描述符1402的稀疏子树描述符1400a的子树条目404a的地址通过子树索引312a转发到子树存储器400a。所选择的子树条目404a中存储的数据字段406和指针字段408通过子树数据412a和子树指针414a转发到映射程序地址逻辑402a。映射程序地址逻辑402a生成存储了s5的子树条目的映射程序条目504a⁴的映射程序地址416a。映射程序地址416a取决于子树数据412a,子树指针414a和关键字210b的下一部分。把s5的子树条目通过子树索引312b转发到子树存储器400b。子树存储器400b存储子树B₂2006的节点描述符1402b²,1402b¹。子树B₂的稀疏子树描述符1400b¹存储在子树条目404b中。子树条目404b中存储的数据字段406和指针字段408通过子树数据412b和子树指针414b转发到映射程序地址逻辑402b。映射程序地址逻辑402b生成存储了h1的路由条目的映射程序条目504b³的映射程序地址416b。映射程序地址416b取决于子树数据412b,子树指针414b和关键字210c的下一部分确定。为向子树B₂2006添加路由h2,分配子树映射程序418b中一组前面未使用过的映射程序602c,以便存储保存了子树B₂’2008的路由r6,h1和h2的映射程序条目504c²-504c⁴。映射程序条目504c¹存储子树B₂’2008的缺省条目;即,映射程序条目504b¹中存储的相同的值。映射程序条目504c²存储路由r6的路由条目;即,映射程序条目504b²中存储的相同的值。映射程序条目504c³存储路由h1的路由条目;即,映射程序条目504b³中存储的相同的值。映射程序条目504c⁴存储路由h2的路由条目。当写入映射程序条目504c^1-4块时,可以通过子树映射程序418a中的504a⁴中为路由s5存储的子树条目来访问映射程序条目504b¹-504b³中存储的路由条目。在子树映射程序418b中已存储了子树B₂’2008的映射程序条目504c^1-4后,把稀疏子树描述符1400c¹添加到子树存储器400b。节点描述符1402c^1-3的数量少于16,因此,节点描述符1402c^1-3存储在稀疏子树描述符1400c¹中。子树描述符1400¹在子树存储器400b中的位置取决于与稀疏子树描述符1400c¹有关的节点描述符1402c^1-3的熟练。通过在子树B₂2006中增加一个新路由,要为稀疏子树描述符1400c¹存储的节点描述符1402c¹-1402c³的数量从2增加到3。稀疏子树描述符1400c¹存储在每个稀疏子树描述符含有3个节点描述符的子树条目404c中,并且将模式字段1404设置为“2”。如果有可用空间或分配了新模式3的子树条目,那么稀疏子树描述符1400c¹存储在当前模式3的子树条目404c中。子树B₂’2008中路由的节点描述符存储在模式3的子树条目404c中稀疏子树描述符1400c¹中的节点描述符1402c^1-3中。把稀疏子树描述符1400c¹和节点描述符1402c^1-3存储到子树存储器400b后,可以访问子树B₂’2008。为提供对子树B₂’2008的访问,修改子树条目504a⁴在索引子树条目404c中索引稀疏子树描述符1400b¹而不是在子树条目404b中索引稀疏子树描述符1400c¹。可以访问映射程序条目504c⁴中存储的路由h2的路由条目和相应映射程序条目504c²和504c³中分别存储的路由r6和h1。由于不能再访问映射程序条目504b¹-504b³,所以将它们释放并放置在空闲列表(未示出)中等待以后分配。另外,也不能再访问稀疏子树描述符1400b¹。因此,稀疏子树描述符1400b¹被释放并放置在空闲列表(未显示)中等待以后分配。已经描述了向稀疏子树中增加路由。也可以通过在新分配的子树条目404中存储新的密集子树描述符以及在子树映射程序418中存储对应的映射程序条目,并且将映射程序条目504a⁴中存储的子树条目改为索引新分配的子树条目404来向密集子树中增加路由。图26是说明在图25所示查找表200中执行增加路由的递增更新步骤的流程图。在步骤2200中,计算每个子树的路由数量以确定路由更新产生稀疏子树还是密集子树。如果路由更新后为密集子树,处理过程继续到步骤2218。如果路由更新后为稀疏子树,处理过程继续到步骤2202。在步骤2202中,子树是稀疏的,因此确定为稀疏子树模式。处理过程继续到步骤2204。在步骤2204中,搜索子树映射程序418(图5)中存储的部分填充的子树条目404的列表以确定是否可将新的稀疏子树描述符1400c¹存储在前面分配的子树条目404中。例如,可将4个稀疏子树描述符1400c¹-1400c⁴存储在模式4的子树条目404中。如果只存储了3个,子树条目404被部分填充并且存储在部分填充的子树条目404的列表中。如果有可用的部分填充的子树条目404,处理过程继续到步骤2208。否则,处理过程继续到步骤2206。在步骤2206中,分配新的子树条目404c以便存储稀疏子树描述符1400c¹,并且在为新分配的子树条目404c中的稀疏子树描述符1400c¹中存储的节点描述符1402c¹-1402c³存储映射程序条目504(图6B)的子树映射程序中分配映射程序条目504c¹-504c⁴。把指向子树映射程序418(图5)中分配的映射程序条目504c¹-504c⁴块的指针存储在新子树条目404c的指针字段408中。处理过程继续到步骤2208。在步骤2208中,从子树条目404c中指针字段408中存储的指针和子树条目404c中模式字段1404中存储的模式来确定稀疏子树描述符1400c¹的子树映射程序中第一个映射程序条目504c¹的位置。处理过程继续到步骤2210。在步骤2210中,将稀疏子树的路由条目存储在子树映射程序418b中的映射程序条目504c¹-504c⁴中。处理过程继续到步骤2212。在步骤2212中,把存储节点描述符1402c¹-1402c³的稀疏子树描述符1400c¹存储在子树条目404c中。处理过程继续到步骤2214。在步骤2214中,映射程序条目504a⁴中存储的子树条目描述符304(图4)被修改为索引子树条目404c中存储的新稀疏子树描述符1400c¹。现在可以访问映射程序条目504c⁴中存储的h2的路由条目。处理过程继续到步骤2216。在步骤2216中,不能再访问映射程序条目504b¹-504b³和稀疏子树描述符1400b。将映射程序条目504b¹-504b³放置在子树映射程序418b的映射程序条目504(图6B)的空闲列表中并且分配用来存储其它路由。在部分填充的子树条目的列表中更新子树条目404b中的第一个可用位置。处理过程结束。在步骤2218中,从处理器存储器2400(图24)中存储的空闲子树条目404的列表分配一个新的子树条目404。分配新的子树条目404用来存储新的密集子树描述符。分配子树映射程序418b中的映射程序条目组504(图6B)用于存储这些路由。指向若干块已分配的映射程序条目504(图6B)的指针存储在子树条目404(图5)中的指针字段408(图7)中。处理过程继续到步骤2220。在步骤2220中,如前面结合图6A-B描述的,将新的密集子树描述符写入新子树条目404中的数据字段406。处理过程继续到步骤2222。在步骤2222中,把密集子树的路由条目存储在由子树条目404中的指针字段408中存储的指针所识别的子树映射程序418(图5)中的映射程序条目504(图6B)中。处理过程继续到步骤2224。在步骤2224中,修改映射程序条目504a⁴中存储的子树条目描述符304(图4)以指向新的子树条目404c中存储的新密集子树描述符。现在可以访问映射程序条目504c⁴中存储的h2的路由条目。处理过程继续到步骤2226。在步骤2226中,把由旧子树条目404中的指针字段408中存储的指针指向的映射程序条目504(图6B)返回到处理器存储器2400(图24)中存储的映射程序条目的空闲列表。旧的子树条目404b添加到处理器存储器2400(图24)中存储的空闲子树条目列表中。已经描述了向查找表添加路由的过程。执行类似的过程以便从查找表删除路由。例如,从子树B₂’2008中删除h2xa0504c⁴需要存储含有路由r6和h1的两个节点描述符的新稀疏子树描述符,在模式2的子树条目中存储稀疏子树描述符,更新对应的子树映射程序并且习惯映射程序条目504a⁴中存储的子树条目描述符304(图4)指向新子树条目404中存储的更新的子树描述符。虽然已经参考优选实施例特别给出和描述了本发明,本领域技术人员可以理解,在不脱离本发明所附权利要求的范围的情况下可以对本发明的形式和细节进行改变。